// https://www.lintcode.com/problem/partition-array/

public class Solution {
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        // write your code here
        if (nums.length == 0) {
            return 0;
        }
        int start = 0, end = nums.length - 1;
        while (start < end) {
            if (nums[start] < k) {
                ++start;
            } else if (nums[end] >= k) {
                --end;
            } else {
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
                ++start;
                --end;
            }
        }
        return (nums[start] < k) ? (start + 1) : start;
    }
}